package com.cwj.lab2;

import com.cwj.lab1.myArrayList;

import java.util.HashMap;
import java.util.function.Supplier;

public class HFMTree<T> {
//    private myArrayList<Node> list
    //存放哈夫曼树的数组
    private myArrayList<Node<T>> list=null;
    //哈夫曼树结点
   public static class Node<T> {
        T data;
        int val;
        int parent;//其父母结点
        int lef;//左子结点
        int rig;//右子结点

        public Node(T data, int val, int parent, int lef, int rig) {
            this.data = data;
            this.val = val;
            this.parent = parent;
            this.lef = lef;
            this.rig = rig;
        }

       public Node() {
           this.data=null;
           val=parent=lef=rig=-1;
       }
   }
/**
 * 通过传入一个哈希表：代表数据和其频数；构造一颗哈夫曼树
 * */
    public void creatTree(Supplier<Node<T>>supper, HashMap<T, Integer> map) {
        this.list =new myArrayList<Node<T>>(2*map.size());
        for(int i=0;i<2*map.size();i+=1){
            this.list.addLast(supper.get());
        }
//        int i=1;
        Node node = null;
        int top=1;
        for (T cc : map.keySet()) {
            node=this.list.get(top++);
            node.data = cc;
            node.val = map.get(cc);
            node.lef = node.rig = node.parent = -1;
        }
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MIN_VALUE;
        int ind_1 = -1;
        int ind_2 = -1;
        int N = map.size();
        for (int i = 1; i < N; i += 1) {
            min1=min2=Integer.MAX_VALUE;
            ind_1=ind_2=-1;
            for (int j = 1; j < i + N; j++) {
                Node nn = this.list.get(j) ;
                if (nn.parent == -1 && nn.val < min1) {
                    min2 = min1;
                    ind_2 = ind_1;
                    min1 = nn.val;
                    ind_1 = j;
                } else if (nn.parent == -1 && nn.val < min2) {
                    min2 = nn.val;
                    ind_2 = j;
                }
            }
            Node temp = this.list.get(i + N);
            temp.val = min1 + min2;
            temp.lef = ind_1;
            temp.rig = ind_2;
            this.list.get(ind_1).parent = i + N;
            this.list.get(ind_2).parent = i + N;
        }
    }
/**
 * 利用该函数可以得到每个结点的哈夫曼编码
 * 原理即：记录每个叶子结点的到根结点的路径
 * 用过遍历回溯可以完成
 * */
    public HashMap<T, myArrayList<Character>> getCode() {
        //sb的由来是StringBuffer的缩写
        myArrayList<Character> sb = new myArrayList<>();
        HashMap<T, myArrayList<Character>> table = new HashMap<>();
        getCode(this.list.size() - 1, sb, table);
        return table;
    }

    private void getCode(int ind, myArrayList<Character> sb, HashMap<T, myArrayList<Character>> table) {
        Node<T> node = this.list.get(ind);
        if (node.lef == -1 && node.rig == -1) {
//            System.out.println("node.data="+node.data);
            try {
                table.put(node.data, (myArrayList<Character>) sb.clone());
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
        }
        if (node.lef != -1) {
            sb.addLast('0');
            getCode(node.lef, sb, table);
            sb.delLast();
        }
        if (node.rig != -1) {
            sb.addLast('1');
            getCode(node.rig, sb, table);
            sb.delLast();
        }
    }


}
